package Link;

public class leet_25 {
    public static void main(String[] args) {
        ListNode one = new ListNode(1);
        ListNode two = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);

        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;

        Solution_25 p = new Solution_25();
        ListNode value = p.reverseKGroup(one, 3);

        while(value!=null){
            System.out.println(value.val);
            value = value.next;
        }

    }
}


/**
 *    这个问题本质逻辑很清晰
 *    [1 2 3 4]  ,2
 *    结果就是 [2 1 4 3]
 *
 *    那么首先要知道一个链表可以翻转几次
 *    times = length/n
 *
 *
 *    第一个问题如何设计返回指针？
 *    然后发现 加上一个 虚拟的结点会让问题简单化
 *    [hair, 1, 2, 3, 4] ->>  [hair, 2, 1, 4, 3]
 *    可以放心的返回一个 hair.next 就可以了
 *
 *    第二个问题如何设计翻转与翻转后的链表合并问题？
 *    本身存在结点 head 翻转 前 的头结点
 *    新增结点 pre 结点是 head的前一个结点
 *    新增结点 tail 是翻转 前 的尾结点
 *    新增结点nex 结点是尾结点的下一个节点
 *    当我们翻转结束后 理论上 只需要将
 *    tail 与 head 翻转
 *    pre.next = tail
 *    head.next = nex
 *    就完成了翻转与拼接
 *    然后将
 *    pre = head
 *    head = nex 就可以继续翻转k元素
 *    直到 head 为空 或者 head后面元素不足k个。
 */
class Solution_25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 首先建立头指针
        ListNode hair = new ListNode(0);
        hair.next = head;
        // 需要翻转的前一个Node
        ListNode pre = hair;

        // head的下一个节点不为空
        while(head!=null){
            // 需要翻转的尾Node
            ListNode tail = pre;
            // 找到尾
            for(int i=0; i<k; i++){
                tail = tail.next;
                // 剩下的数量没办法翻转了
                if(tail==null){
                    return hair.next;
                }
            }
            // 需要翻转的尾Node的下一个节点
            ListNode nex = tail.next;
            // 开始翻转k列表
            ListNode[] listNodes = reverseLinkNode(head, k);
            // 将翻转的链表拼接上  0-1-2-3 翻转1-2： 结果是0-2-1-3
            // 所以传出来的结果 pre 指向第一个节点
            // 第二个节点指向 nex
            head = listNodes[0];
            tail = listNodes[1];

            pre.next = head;
            tail.next = nex;

            head = nex;
            pre = tail;
        }
        return hair.next;
    }

    /**
     * 翻转链表 参考leetcode 206 题
     * @param head  翻转的头结点
     * @param k    需要遍历的次数
     */
    public ListNode[] reverseLinkNode(ListNode head, int k){
        ListNode prev = null;
        ListNode curr = head;
        // 翻转次数
        for(int i=0; i<k; i++){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return new ListNode[]{prev, head};
    }
}


